The rise of multimedia computing appliances and digital video transmission has led to an increased need to store and manipulate many-colored and complex digital images. Examples of many-colored and complex digital images include: digital photographic images of the natural world, whether taken with a digital camera or digitized from an analog camera print; computer-generated images of the natural world; and/or computer-generated images which include anti-aliased text or graphics.
In particular, anti-aliased images are increasing in both frequency of occurrence and importance in the art. This is primarily due to the increased expectations regarding visual appearance of the user interface in word processing and other text and/or graphic orientated programs. Anti-aliasing is a technique well known to those of skill in the art whereby the edges of an image are blurred or “softened” to reduce the visual artifacts produced by finite pixel sizes.
Due to the complexity of digital images, it is often necessary to compress the images in order to save storage space and/or minimize bandwidth when storing or transmitting the digital images. The compression/decompression process typically uses standardized algorithms well known to those of skill in the art. The algorithms for compressing and decompressing the images are known generically as COmpressor/DECompressors or “codecs”.
Codecs are typically grouped into two main types; lossless and lossy. Lossless codecs, like LZ coding and GIF, preserve the image information in its exact form. While providing virtually perfect image replication capabilities, lossless codecs tend to provide less compression opportunities and require more resources, such as storage space and transmission bandwidth, to employ. On the other hand, lossy codecs, such as JPEG and vector quantization, store only an approximate representation of the image. Lossy codecs are typically formulated based on the capabilities and limitations of the human visual system to detect subtle differences in color. In other words, granularity and detail beyond that capable of being detected by the human eye are disregarded and do not survive the compression process. Since, using lossy codecs, digital information is selectively discarded, lossy codecs typically achieve much better compression than lossless codecs while still maintaining acceptable image quality.
In addition to the true multi-colored images, many anti-aliased images of only two base colors are also of great importance. However, in the prior art, two color anti aliased images were typically treated as many colored images by traditional encoding mechanisms. This is because while many anti-aliased images, such as those resulting from anti-aliasing two color text images or designs, have a low inherent information content, i.e., two base colors with shading variations thereof, the images appear to traditional encoding mechanisms as many colored images with a complexity similar to that of a natural image.
FIG. 1A shows an example of an image 100 including a stylized text letter “R” 101. The pixels making up image 100 are typically read horizontally line-by-line, left to right and top-to-bottom in a wrap around manner. Consequently, horizontal lines of pixels 1 to 20 are read from A to M in a continuous flow. As an example, horizontal line 1 is read from A to M and horizontal line 2 is read from A to M. Then horizontal line 3 is read from A to M and horizontal line 4 is read from A to M. Then horizontal line 5 is read from A to M and horizontal line 6 is read from A to M. Then horizontal line 7 is read from A to M and horizontal line 8 is read from A to M. Then horizontal line 9 is read from A to M and horizontal line 10 is read from A to M. Then horizontal line 11 is read from A to M and horizontal line 12 is read from A to M. Then horizontal line 13 is read from A to M and horizontal line 14 is read from A to M. Then horizontal line 15 is read from A to M and horizontal line 16 is read from A to M. Then horizontal line 17 is read from A to M and horizontal line 18 is read from A to M. Then horizontal line 19 is read from A to M and, finally, horizontal line 20 is read from A to M. As noted above, horizontal lines of pixels 1 to 20 are typically scanned as described above and are then read in a continuous flow of pixels for the entire image.
As described above, when a horizontal line of a text figure is read, there are typically series or runs of identical pixels. As an example, in FIG. 1A, when horizontal line 10 is read from A to M in the direction shown by arrow 105, pixels 10A, 10B and 10C make up a first run of three pixels of the first pixel color, in this example white, while pixels 10D, 10E, 10F, 10G, 10H, 10I and 10J make up a run of seven pixels of a second pixel color, in this example black, and pixels 10K, 10L and 10M make up a second run of three pixels of the first pixel color, in this example white.
In the example above, absent compression, each of the thirteen pixels 10A to 10M was treated as a new color being one of 256^3 possibilities, requiring three bytes of data per pixel. Consequently, absent some compression mechanism, thirty-nine bytes would be required to represent thirteen pixels of two colors arranged in runs, i.e., thirteen pixels times three bytes per pixel. Clearly this was an inefficient use of resources and, as noted, the cumulative effect for an actual image composed of hundreds, or thousands, of pixels is far more problematic than the simple example above indicates.
In addition, as can be seen in FIG. 1A, a similar result is obtained when reading image 100 by vertical columns of pixels, top-to-bottom in a vertical direction. In this instance, image 100 is typically read column-by-column, top-to-bottom and left to right in a wrap around manner. As an example, vertical column A is read from 1 to 20 and vertical column B is read from 1 to 20. Then vertical column C is read from 1 to 20 and vertical column D is read from 1 to 20. Then, vertical column E is read from 1 to 20 and vertical column F is read from 1 to 20. Then vertical column G is read from 1 to 20 and vertical column H is read from 1 to 20. Then, vertical column I is read from 1 to 20 and vertical column J is read from 1 to 20. Then vertical column K is read from 1 to 20 and vertical column L is read from 1 to 20. Then, finally, vertical column M is read from 1 to 20.
As with the reading of horizontal lines of pixels discussed above, when a vertical column of a text figure is read, there are also runs of identical pixels. As an example, in FIG. 1A, when vertical column E is read from 1 to 20 in the direction shown by arrow 107, pixels E1 and E2 make up a run of two pixels of a first pixel color, in this example white, while pixels E3, E4, E5, E6, E7, E8, E9, E10, E11, E12, E13, E14, E15, E16, E17 and E18 make up a run of sixteen pixels of a second pixel color, in this example black, and pixels E19 and E20 make up a second run of two pixels of the first pixel color, in this example white.
As with the horizontal example above, in the prior art, absent some compression mechanism, each of the twenty pixels E1, E2, E3, E4, E5, E6, E7, E8, E9, E10, E11, E12, E13, E14, E15, E16, E17, E18, E19 and E20 was treated as a new color being one of 256^3 possibilities, requiring three bytes of data per pixel. Consequently, even in this highly simplified, and low volume, example, absent compression, sixty bytes would be required to represent twenty pixels of two colors arranged in runs, i.e., twenty pixels times three bytes per pixel.
In addition, as shown in FIG. 1A, there can exist transition pixels between pixel runs. Transition pixels can be of more than one transition color, such as pixels 4C, 5L, 9F, 13H, 13J, and 17C versus pixels 3K, 4F, 4G, 4H, 4I, 4L, 5C, 6J, 7J, 8I, 8L, 12J, 14H, 16C, 16K, 17F and 17I in FIG. 1A, but the transition pixels typically lie on a line in RGB space connecting the two base colors and are therefore merely shades of the two base colors.
In instances where transition pixels are present, runs of these transition pixels also often occur, such as the run including 4F, 4G, 4H, 4I. However, once again, in the prior art, absent a compression mechanism, these runs were ignored and each transition pixel was also treated as a new color being one of 256^3 possibilities, requiring three bytes of data per pixel.
What is needed is a method of compressing and decompressing two-color anti aliased images so these extremely common anti-aliased images can be more efficiently compressed.